from typing import List


class Solution:
    def bestRotation(self, array: List[int]) -> int:
        size = len(array)

        # 定义差分数组
        nums = [0] * size

        for i, num in enumerate(array):
            left = (i - num + 1) % size
            right = (i + 1) % size
            nums[left] -= 1
            nums[right] += 1
            if left > right:
                nums[0] -= 1

        ans_idx, ans_val = 0, -size
        now = 0
        for i, num in enumerate(nums):
            now += num
            if now > ans_val:
                ans_idx, ans_val = i, now
        return ans_idx


if __name__ == "__main__":
    print(Solution().bestRotation([2, 3, 1, 4, 0]))  # 3
    print(Solution().bestRotation([1, 3, 0, 2, 4]))  # 0
